package leetcodev1.字符串;

import leetcodev1.链表.Solution;

public class LeetCode67 {
    //1.暴力解 转换成数字相加后 在转换成2进制字符串
    //2.直接进位+
    public String addBinary(String a, String b) {
        int aLength = a.length(), bLength = b.length(), aIndex = aLength - 1, bIndex = aIndex + (bLength - aLength);
        boolean needUp = false;
        StringBuilder sb = new StringBuilder();
        while (aIndex >= 0 || bIndex >= 0) {
            char aChar = aIndex < 0 ? '0' : a.charAt(aIndex);
            char bChar = bIndex < 0 ? '0' : b.charAt(bIndex);
            int num = (aChar - '0') + (bChar - '0') + (needUp ? 1 : 0);
            if (num >= 2) {
                num -= 2;
                needUp = true;
            } else {
                needUp = false;
            }

            sb.append(num);
            aIndex--;
            bIndex--;
        }

        if (needUp) {
            sb.append('1');
        }
        return sb.reverse().toString();
    }

    //先转数字后计算
    public String addBinary1(String a, String b) {
        return Integer.toBinaryString(
                Integer.parseInt(a, 2) + Integer.parseInt(b, 2)
        );
    }

    //写法更干净一点
    //主要进位不需要用bool单独维护
    //当前位+carry % 2
    //下一位+（carry /= 2）
    public String addBinary2(String a, String b) {
        StringBuffer ans = new StringBuffer();

        int n = Math.max(a.length(), b.length()), carry = 0;
        for (int i = 0; i < n; ++i) {
            carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
            carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
            ans.append((char) (carry % 2 + '0'));
            carry /= 2;//carry代替need up
        }

        if (carry > 0) {
            ans.append('1');
        }
        ans.reverse();

        return ans.toString();
    }

}
